// 给定两个整数数组nums1，nums2，要求：计算两个数组中公共的，长度最长的子数组长度
// 子数组：数组的连续子序列

// 思路，动态规划
// 思路1，二维数组`dp[i][j]`表示下标为i-1的A和下标为j-1的B的最长重复子树组

function findLength(nums1, nums2) {
    let dp = new Array(nums1.length + 1).fill(0).map(item => new Array(nums2.length + 1).fill(0))
    let result = 0
    for (let i = 1; i <= nums1.length; i++) {
        for (let j = 1; j <= nums2.length; j++) {
            if (nums1[i - 1] === nums2[j - 1]) {
                dp[i][j] = dp[i-1][j-1] + 1
                result = Math.max(result, dp[i][j])
            }            
        }
    }
    return result
}

let nums1 = [1, 2, 3, 2, 1], nums2 = [3, 2, 1, 4, 7]

console.log(findLength(nums1, nums2))

// 思路2，滚动数组，用一维数组代替二维数组
// 遍历里层数组的时候要从后向前遍历，避免重复覆盖
function findLength2(nums1, nums2) {
    let dp = new Array(nums2.length + 1).fill(0)
    let result = 0
    for (let i = 1; i <= nums1.length; i++) {
        // 这是因为在每一步，我们只需要当前行和上一行的信息
        // ，所以可以将dp数组“滚动”使用，即在计算完当前行后，
        // 将下一行的信息写入同一个数组，覆盖掉之前的行。
        for (let j = nums2.length; j >= 1; j--) {
            if (nums1[i-1] === nums2[j-1]) {
                dp[j] = dp[j-1] + 1
            } else {
                dp[j] = 0
            }
            result = Math.max(result, dp[j])          
        }
    }
    return result
}

console.log(findLength2(nums1, nums2))